#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int largestSubArea(vector<int>::iterator be, vector<int>::iterator en){
	if(be == en){
		return 0;
	}
	if(en-be == 1){
		return *be;
	}
	// find shortest
	int shortest = 0x7FFFFFFF;
	vector<int>::iterator mid;
	// iter
	for(vector<int>::iterator it = be;
		it != en;
		++it){
		
		if(*it < shortest){
			shortest = *it;
			mid = it;
		}
	}
	// self
	int maxArea = (en - be) * (*mid);
	// left
	int maxLeft = 0;
	if(mid != be){
		maxLeft = largestSubArea(be, mid);
		if(maxLeft > maxArea){
			maxArea = maxLeft;
		}
	}
	// right
	int maxRight = 0;
	if(mid != en-1){
		maxRight = largestSubArea(mid+1, en);
		if(maxRight > maxArea){
			maxArea = maxRight;
		}
	}
	return maxArea;
}


int largestRectangleArea(vector<int> &height) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function

	return largestSubArea(height.begin(), height.end());
}

int largestRectangleArea1(vector<int> &height){
	stack<int> indexStack;
	stack<int> heightStack;
	int res = 0;
	for(int i=0; i<height.size(); ++i){
		int curHeight = height[i];
		if(heightStack.size() == 0 || curHeight >= heightStack.top()){
			indexStack.push(i);
			heightStack.push(curHeight);
		}
		else{
			int theIndex = 0;
			while(heightStack.size()>0 && heightStack.top()>curHeight){
				int theHeight = heightStack.top();
				heightStack.pop();
				theIndex = indexStack.top();
				indexStack.pop();
				int theArea = theHeight * (i - theIndex);
				if(theArea > res){
					res = theArea;
				}
			}
			indexStack.push(theIndex);
			heightStack.push(curHeight);
		}
	}
	while(heightStack.size() > 0){
		int theHeight = heightStack.top();
		heightStack.pop();
		int theIndex = indexStack.top();
		indexStack.pop();
		int theArea = theHeight * (height.size() - theIndex);
		if(theArea > res){
			res = theArea;
		}
	}
	return res;
}


int main(){

	vector<int> vec;
	vec.push_back(2);
	vec.push_back(1);
	vec.push_back(5);
	vec.push_back(6);
	vec.push_back(2);
	vec.push_back(3);
	cout<<largestRectangleArea1(vec)<<endl;

	return 0;
}